P8819 [CSP-S 2022] 星战

发表于 更新于 分类于 ， ， 阅读次数： 作者 Pomelorin

注：上一次写题解是 2022-03-26，那是退役前的最后一篇题解。

虽然我已经退役了，但是我还是要把这个神奇的题搞一搞！

CCF 用以造数据的脚恐怖如斯，如同加工老坛酸菜。

题意

在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

  1. 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
  2. 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

  • A 型特种部队则可以将某个特定的虫洞修复。
  • B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

  • 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
  • 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
  • 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。

点击查看简略题面

给定 \(n\) 个点 \(m\) 条边的有向图，以及四种操作，共 \(q\) 条：

  1. 删除某条边；
  2. 删除以某个点为终点的所有边；
  3. 恢复某条边；
  4. 恢复以某个点为终点的所有边。

“恢复”指恢复原先删过的边，初始时就不存在的边当然不会恢复。

每次操作后，询问是否满足所有的点出度均为 \(1\)。

是不是很简略？

对于所有数据保证：\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。

点击查看题解

题解

45 pts

不可以，总司令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	ll n,m,q,u,v;
	void main()
	{
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=m;i++) scanf("%lld%lld",&u,&v);
		scanf("%lld",&q);
		for(ll i=1;i<=q;i++) printf("NO\n");
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}

真的是部分分

最暴力的做法，对于每次 \(O(n)\) 的修改后，\(O(n)\) 扫一遍看是不是所有点出度都是 \(1\) ，\(O(n^2)\) 枚举所有点判环。

稍微思考之后，即可发现无需判环，因为第一个条件满足后，图即为基环内向树森林。非常详细地充满废话地证明一下：

先讨论图为连通图的情况。所有点出度都是 \(1\)，也就是一定有 \(n\) 条边（\(n\) 为点数）。考虑先分配 \(n-1\) 条无向边，这样形成的是一棵树。给边加方向，由于出度都是 \(1\)，所以只允许“多指向一”的结构。这样，必定剩下根的出度是零。再给根分配余下的一条有向边，无论这条边指向的是哪个点，一定形成了一个环。由于第一次分配确保所有点都可以到达根，保证了所有点一定能到达环，所以形成的图必定是一棵基环内向树。

如果图不连通，则必由连通子图组成。由于所有点出度都是 \(1\)，所以子图中有多少点就有多少边。故亦可按照上面的逻辑证明。

这样呢，由于免去了判环，我们就有了 \(O(n^2)\) 的做法。

100 pts

旧版题解收折

旧版题解表述不清。

实际上，按照原题面，要让总司令可以的条件有两个：

  • 所有的点出度均为 \(1\)。
  • 从任意一个点出发，可以走到一个环中。

但是，第一个条件可以推出第二个条件。证明：

所有点出度均为 \(1\) 意味着图必是一个基环内向树森林，所以从任意一个点出发肯定会走到一个环。

从另一方面证明，所有点出度均为 \(1\) 意味着你从任意一个点出发，存在一条路径，经过了至少 \(n\) 条边。那么路径中必然就存在重复经过的点了。

所以第二个条件是坑人的！根本不需要判环！我们只需判断何时所有的点出度均为 \(1\)。

首先想到直接按题意模拟，记录每个点出度个数。删掉一条边，前驱点出度减一。这样，操作 2 和 4 时间复杂度 \(O(n)\)。暴力判断，复杂度也是 \(O(n)\)，这样得到 \(O(qn)\) 的算法。

发现维护入度可以做到 \(O(1)\) 维护，而可以同时维护所有点的出度之和（入度和=出度和）。

显然，所有的点出度均为 \(1\) 可以推出出度和是 \(n\)，但是不能反推。

怎么办？哈希！

对每一个点随机一个权值。定义 \(f(u)\) 为结点 \(u\) 的前驱点权之和。\(f(u)\) 是可以被非常容易地维护的。另外定义变量 \(sum\) 为所有节点的前驱点权之和，也就是 \(\sum f(u)\)。

显然，所有的点出度均为 \(1\) 时，\(sum\) 的值就等于所有点的点权之和。但是不能反推。

怎么就显然了？？？

此时，对于任意一个结点 \(u\)，有且只有一个结点 \(v\)，满足有向边 \(<u,v>\) 存在。这样，\(u\) 的点权会且只会贡献一次，贡献给 \(f(v)\)。这样，\(sum\) 的值自然就等于所有点的点权之和了。

虽然不能反推，但是当 \(sum\) 的值等于所有点的点权之和时，很大概率满足所有的点出度均为 \(1\)。如果不放心，可以写多重哈希。

这样，这道题就解决了。

我们不想每次操作完之后，都要进行一遍线性复杂度的判断。我们不想让维护操作的复杂度为线性。达到这两个目标之后，就会有线性的正解做法了。

一个自然的想法是，我们能不能记录出度和呢？所有点的出度都是 \(1\)，可以推出出度和为 \(1\)；但是反过来不一定对。但是，我们可以碰碰运气试一试。

记录出度和，就是记录有多少边。考虑所有点的出度不易维护，而入度很好维护，可以维护所有点的入度，进而维护边数。具体地，维护一个存储所有点目前入度的数组 a[]，以及一个变量 cnt，记录全局边数。对于边的操作，直接改就行；对于点的操作，删点就是对应的 a[i] 置为零，恢复点的操作就是让对应地的 a[i] 置为初始值。进行这些操作的同时，cnt 也可以一并维护。每次操作维护之后，判断 cnt 是不是等于 n。这样，时间复杂度就是线性的。

但是这样做，准确率太低了！怎么办？提高准确率！怎么提高？用哈希！

完了。这样你就可以 AC 了。

怎么哈？考虑到根据边数，显然无法判断这些边是不是有的是同一个点发出的。如何解决？给每一条边都赋予一个哈希值，使得同一个点发出的边的哈希值相等（实现时，是直接给点赋哈希值）。把上面数组、变量的意义都由原来的和改为哈希值和。每次操作维护之后，判断 cnt 是不是等于所有点的哈希值和。如果等于，那么表明什么呢？那就表明 cnt 大概率是 n 条由 n 个互不相同的点发出的边的哈希值和。那不就是表示这 n 个点的出度都是一嘛。

这样，这道题就做完了。本题是一个阅读理解+套路题，首先需要提炼信息；然后，给点赋哈希值的 trick，是我所从来没碰到过的，也是没有想出过的。所以此题虽然数据极水，价值还是有的。

代码实现非常容易。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=500000+10;
	ll n,m,q,a[N],in[N],tmp[N],jud=0,now=0;
	mt19937 rnd(time(0));
	ll rand(){return rnd()%N;}
	void main()
	{
		ll u,v,t;
		scanf("%lld%lld",&n,&m);
		for(ll i=1;i<=n;i++)
		{
			a[i]=rand();
			jud+=a[i];
		}
		for(ll i=1;i<=m;i++)
		{
			scanf("%lld%lld",&u,&v);
			in[v]+=a[u]; tmp[v]+=a[u];
			now+=a[u];
		}
		scanf("%lld",&q);
		for(ll i=1;i<=q;i++)
		{
			scanf("%lld",&t);
			if(t==1)
			{
				scanf("%lld%lld",&u,&v);
				now-=a[u]; tmp[v]-=a[u];
			}
			else if(t==2)
			{
				scanf("%lld",&u);
				now-=tmp[u]; tmp[u]=0;
			}
			else if(t==3)
			{
				scanf("%lld%lld",&u,&v);
				now+=a[u]; tmp[v]+=a[u];
			}
			else
			{
				scanf("%lld",&u);
				now+=in[u]-tmp[u]; tmp[u]=in[u];
			}
			if(jud==now) printf("YES\n");
			else printf("NO\n");
		}
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
点击查看简略代码

本段代码来自于：https://www.luogu.com.cn/record/94328325。

1
2
3
#import<iostream>
#define t std::cin>>n
int n,m,r[1<<20],w[1<<20],s,k;main(){for(t>>m,s=n*=n+3;m--;w[k]=r[k]+=++n,s-=n*2)t>>k;for(t;t>>k;s+=m*2,w[n]-=m,puts(s?"NO":"YES"))m=n&1?++k*=2-n,t,k:w[k]-n/4*r[n=k];}